package com.mgq.algorithm.greedy;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.WeakHashMap;

/**
 * 最大资本
 * 假设 力扣（LeetCode）即将开始 IPO 。为了以更高的价格将股票卖给风险投资公司，力扣 希望在 IPO 之前开展一些项目以增加其资本。
 * 由于资源有限，它只能在 IPO 之前完成最多 k 个不同的项目。帮助 力扣 设计完成最多 k 个不同项目后得到最大总资本的方式。
 * 给你 n 个项目。对于每个项目 i ，它都有一个纯利润 profits[i] ，和启动该项目需要的最小资本 capital[i] 。
 * 最初，你的资本为 w 。当你完成一个项目时，你将获得纯利润，且利润将被添加到你的总资本中。
 * 总而言之，从给定项目中选择 最多 k 个不同项目的列表，以 最大化最终资本 ，并输出最终可获得的最多资本。
 * 答案保证在 32 位有符号整数范围内。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/ipo
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class MaxCapital {
    /**
     * 需要使用到堆来解决
     * 小根堆保存所有的项目,然后按照资本capital来进行排序
     * 大根堆保存所有项目收益,按照收益进行排序
     * 然后大根堆弹出的时候就是收益最大的. 小根堆每次加入的都是话费小于等于当前资金的
     * @param k       轮回
     * @param w       初始资金
     * @param profit  收益
     * @param capital 所需要的资本
     * @return
     */
    public static int findMaximizedCapital(int k, int w, int[] profit, int[] capital) {
        PriorityQueue<Node> minCost = new PriorityQueue<>(new MinCostComparator());
        PriorityQueue<Node> maxProfit = new PriorityQueue<>(new MaxCapitalComparator());
        for (int i = 0; i < profit.length; i++) {
            minCost.add(new Node(capital[i], profit[i]));
        }
        for (int i = 0; i < k; i++) {
            while (!minCost.isEmpty() && minCost.peek().cost <= w) {
                maxProfit.add(minCost.poll());
            }
            if (maxProfit.isEmpty()) {
                return w;
            }
            w += maxProfit.poll().profit;
        }
        return w;
    }

    /**
     * 使用二维数组实现
     * @param k
     * @param w
     * @param profit
     * @param capital
     * @return
     */
    public static int findMaximizedCapital2(int k, int w, int[] profit, int[] capital) {
        PriorityQueue<Integer> maxProfit = new PriorityQueue<>((o1, o2) -> o2-o1);
        int length = profit.length;
        int[][] arr=new int[length][2];
        int cur=0;
        for (int i = 0; i < length; i++) {
            arr[i][0]=capital[i];
            arr[i][1]=profit[i];
        }
        //表示按照二维数组的第一个元素进行排序
        //如果是第二个 (a,b)->a[1]-b[1]
        Arrays.sort(arr,(a,b)->a[0]-b[0]);
        for (int i = 0; i < k; i++) {
            //能力所及的全加入
            while (cur < length && arr[cur][0] <= w) {
                maxProfit.add(arr[cur][1]);
                cur++;
            }
            if (maxProfit.isEmpty()) {
                return w;
            }
            w+=maxProfit.poll();
        }
        return w;
    }

    public static void main(String[] args) {
        int w = findMaximizedCapital(4, 1, new int[]{1, 4, 3, 7, 2, 10}, new int[]{1, 1, 2, 2, 3, 4});
        System.out.println(w);
        int w2 = findMaximizedCapital2(4, 1, new int[]{1, 4, 3, 7, 2, 10}, new int[]{1, 1, 2, 2, 3, 4});
        System.out.println(w2);
        int[][] arr=new int[3][2];
        arr[0][0]=1;
        arr[0][1]=2;
        arr[1][0]=2;
        arr[1][1]=3;
        arr[2][0]=3;
        arr[2][1]=4;
        //按照数组的第一个元素排序
        Arrays.sort(arr, Comparator.comparingInt(a -> a[0]));
        //System.out.println(Arrays.toString(arr[0]));
    }
}

/**
 * 表示项目
 */
class Node {
    //花费
    int cost;
    //项目的收益
    int profit;

    public Node(int cost, int profit) {
        this.cost = cost;
        this.profit = profit;
    }
}

/**
 * 最小花费比较器
 */
class MinCostComparator implements Comparator<Node> {

    @Override
    public int compare(Node o1, Node o2) {
        return o1.cost - o2.cost;
    }
}

/**
 * 最大资本比较器
 */
class MaxCapitalComparator implements Comparator<Node> {

    @Override
    public int compare(Node o1, Node o2) {
        return o2.profit - o1.profit;
    }
}